#!/usr/bin/env pyhton
# -*- coding: utf-8 -*-


# Projet CellMates
# Judith ROBSON
# Roxane LEVY
# Ludovic JURADO


from bitarray import bitarray
from bisect import insort



class Huffman :
        """
        Classe permettant la compression et la décompression d'une partie de jeu CellMates.  Une partie est représentée sous la forme d'une matrice contenant les N grilles affichées sur l'interface jusqu'au moment de la sauvegarde (N correspondant au nombre d'étapes, par défaut la compression n'est pas sauvegardée dans un fichier)
Il y a deux méthodes à utiliser :
- encode()  : à partir de la matrice, va construire le dico de fréquences, l'arbre de huffman, enregistrer ou non la compression dans un fichier de sauvegarde
- decode() : à partir du prefix et du bitarray construit et retourne la matrice décompressée

Dans cette classe on trouve également :
- une fonction qui retourne un dictionnaire des occurrences des caractères de la matrice
- une fonction qui crée un arbre binaire à partir du dictionnaire d'occurrences
- une fonction qui construit la table des symboles
"""

    def __init__(self) :
        self.matrice = []
        self.prefix = {}
        self.tri = []
        self.huff = bitarray()




    # fonction d'encodage de la matrice
    def encode(self):
        self._triBinaire(self._occurrences())
        self._make_codes(self.tri[0])
        self.huff.encode(self.prefix, self.matrice)





    # une fonction qui retourne un dictionnaire des fréquences d'occurrence de chacun des caractères
    def _occurrences(self) :
        o = {}
        for x in self.matrice : o[x] = o.get(x, 0) + 1
        return o



    # fonction qui crée un arbre de Huffman à partir d'un dico d'occurrences
    def _triBinaire(self, occurrences):
        H = [(occurrences[s], s) for s in occurrences]
        H.sort()
        while H[1:] :
            childL, childR = H.pop(1), H.pop(0)
            parent = (childL[0] + childR[0], childL, childR)
            insort(H, parent)
        self.tri = H



    # fonction qui prend un arbre de Huffman en argument, construit à partir du dictionnaire vide nommé prefix, une nouvelle table associant à chaque symbole le code qui le représentera dans le résultat compressé
    def _make_codes(self, node, code = bitarray()) :
        if (len(node) == 2) : self.prefix[node[1]] = code
        else :
            for i in xrange(2) :
                self._make_codes(node[i+1], code + bitarray([i]))





    # fonction de décodage, elle utilise le code préfixé et la chaîne de bits à décompresser pour retourner la matrice correspondante
    def decode(self):
        self.matrice = ''.join(self.huff.decode(self.prefix))
        return self.matrice

